{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Completing Word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestCompletingWord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短补全词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>licensePlate</code> 和一个字符串数组 <code>words</code> ，请你找出&nbsp;<code>words</code> 中的 <strong>最短补全词</strong> 。</p>\n",
    "\n",
    "<p><strong>补全词 </strong>是一个包含 <code>licensePlate</code> 中所有字母的单词。<strong>忽略</strong>&nbsp;<code>licensePlate</code> 中的 <strong>数字和空格 </strong>。<strong>不区分大小写</strong>。如果某个字母在 <code>licensePlate</code> 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。</p>\n",
    "\n",
    "<p>例如：<code>licensePlate</code><code> = \"aBc 12c\"</code>，那么它的补全词应当包含字母 <code>'a'</code>、<code>'b'</code> （忽略大写）和两个 <code>'c'</code> 。可能的 <strong>补全词</strong> 有 <code>\"abccdef\"</code>、<code>\"caaacab\"</code> 以及 <code>\"cbca\"</code> 。</p>\n",
    "\n",
    "<p>请返回 <code>words</code> 中的 <strong>最短补全词</strong> 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 <code>words</code> 中 <strong>第一个</strong> 出现的那个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>licensePlate = \"1s3 PSt\", words = [\"step\", \"steps\", \"stripe\", \"stepple\"]\n",
    "<strong>输出：</strong>\"steps\"\n",
    "<strong>解释：</strong>最短补全词应该包括 \"s\"、\"p\"、\"s\"（忽略大小写） 以及 \"t\"。\n",
    "\"step\" 包含 \"t\"、\"p\"，但只包含一个 \"s\"，所以它不符合条件。\n",
    "\"steps\" 包含 \"t\"、\"p\" 和两个 \"s\"。\n",
    "\"stripe\" 缺一个 \"s\"。\n",
    "\"stepple\" 缺一个 \"s\"。\n",
    "因此，\"steps\" 是唯一一个包含所有字母的单词，也是本例的答案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>licensePlate = \"1s3 456\", words = [\"looks\", \"pest\", \"stew\", \"show\"]\n",
    "<strong>输出：</strong>\"pest\"\n",
    "<strong>解释：</strong>licensePlate 只包含字母 \"s\" 。所有的单词都包含字母 \"s\" ，其中 \"pest\"、\"stew\"、和 \"show\" 三者最短。答案是 \"pest\" ，因为它是三个单词中在 words 里最靠前的那个。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= licensePlate.length &lt;= 7</code></li>\n",
    "\t<li><code>licensePlate</code> 由数字、大小写字母或空格 <code>' '</code> 组成</li>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 15</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-completing-word](https://leetcode.cn/problems/shortest-completing-word/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-completing-word](https://leetcode.cn/problems/shortest-completing-word/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1s3 PSt\"\\n[\"step\",\"steps\",\"stripe\",\"stepple\"]', '\"1s3 456\"\\n[\"looks\",\"pest\",\"stew\",\"show\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        from collections import Counter\n",
    "        licensePlate = Counter(filter(str.isalpha, licensePlate.lower()))\n",
    "        return min(filter(lambda w: not (licensePlate - Counter(w.lower())), words), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def func(string):\n",
    "            dict_ = {}\n",
    "            set_ = set()\n",
    "            for item in string:\n",
    "                if item in (' ', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ''):\n",
    "                    continue\n",
    "                item = item.lower()\n",
    "                set_.add(item)\n",
    "                if item in dict_.keys():\n",
    "                    dict_[item] += 1\n",
    "                else:\n",
    "                    dict_[item] = 1\n",
    "            return dict_, set_\n",
    "\n",
    "        dict_license, set_license = func(licensePlate)\n",
    "  \n",
    "        lst = [func(item) for item in words]\n",
    "        lst1 = []\n",
    "        for i in range(len(lst)):\n",
    "            if set_license.issubset(lst[i][1]):\n",
    "                flag = True\n",
    "                for k, v in lst[i][0].items():\n",
    "                    if k in dict_license.keys():\n",
    "                        if lst[i][0][k] >= dict_license[k]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            flag = False\n",
    "                            break\n",
    "\n",
    "                if not flag:\n",
    "                    continue\n",
    "                else:\n",
    "                    lst1.append(words[i])\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "        result = ''\n",
    "        len_ = float('inf')\n",
    "        for item in lst1:\n",
    "            if len(item) < len_:\n",
    "                len_ = len(item)\n",
    "                result = item\n",
    "        return result        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: list[str]) -> str:\n",
    "        def count(s):\n",
    "            s = s.lower()\n",
    "            cnts = [0] * 26\n",
    "            for c in s:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    cnts[ord(c) - ord('a')] += 1\n",
    "            return cnts\n",
    "\n",
    "        cs = count(licensePlate)\n",
    "        l = float('inf')\n",
    "        res = None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                ws = count(w)\n",
    "                i = 0\n",
    "                while i < len(cs):\n",
    "                    if ws[i] < cs[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                    if i == len(cs):\n",
    "                        res = w\n",
    "                        l = len(w)\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    licensePlate = \"Ah71752\"\n",
    "    words = [\"suggest\", \"letter\", \"of\", \"husband\", \"easy\", \"education\", \"drug\", \"prevent\", \"writer\", \"old\"]\n",
    "    print(obj.shortestCompletingWord(licensePlate, words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: list[str]) -> str:\n",
    "        def count(s):\n",
    "            sdic = {}\n",
    "            s = s.lower()\n",
    "            for c in s:\n",
    "                if \"a\" <= c <= \"z\":\n",
    "                    if c in sdic:\n",
    "                        sdic[c] += 1\n",
    "                    else:\n",
    "                        sdic[c] = 1\n",
    "            return sdic\n",
    "        licensedic = count(licensePlate)\n",
    "\n",
    "        l = float('inf')\n",
    "        ans = None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                isok = True\n",
    "                wdic = count(w)\n",
    "                for key in licensedic:\n",
    "                    if (key not in wdic) or wdic[key] < licensedic[key]:\n",
    "                        isok = False\n",
    "                        break\n",
    "                if isok:\n",
    "                    ans = w\n",
    "                    l = len(w)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    licensePlate = \"Ah71752\"\n",
    "    words = [\"suggest\", \"letter\", \"of\", \"husband\", \"easy\", \"education\", \"drug\", \"prevent\", \"writer\", \"old\"]\n",
    "    print(obj.shortestCompletingWord(licensePlate, words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        lowers = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        dic = {}\n",
    "        licensePlate = licensePlate.lower()\n",
    "        for i in licensePlate:\n",
    "            if i in lowers:\n",
    "                dic[i] = dic.get(i , 0) + 1\n",
    "        \n",
    "        ans = ''\n",
    "        len_pre = 10000\n",
    "        for k in words:\n",
    "            bools = True\n",
    "            for m in dic:\n",
    "                if dic[m] > k.count(m):\n",
    "                    bools = False\n",
    "                    break\n",
    "            if bools:\n",
    "                if len(k) < len_pre:\n",
    "                    len_pre = len(k)\n",
    "                    ans = k\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        dicts = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        for word in words:\n",
    "            flag = True\n",
    "            for k, v in dicts.items():\n",
    "                if word.count(k) < v:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = sorted(list(filter(lambda x: not (ord(x)>=ord('0') and ord(x)<=ord('9')) and x!=' ', [_ for _ in licensePlate.lower()])))\n",
    "        residx = -1\n",
    "        for idx, word in enumerate(words):\n",
    "            strs = sorted([_ for _ in word])\n",
    "            i, j = 0, 0\n",
    "            while i<len(licensePlate) and j<len(strs):\n",
    "                if licensePlate[i] == strs[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    while j<len(strs) and licensePlate[i] != strs[j]:\n",
    "                        j += 1\n",
    "            if i==len(licensePlate):\n",
    "                if residx==-1 or len(word)<len(words[residx]):\n",
    "                    residx = idx\n",
    "        return words[residx]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def counter(word):\n",
    "            cnts = [0] * 26\n",
    "            for c in word:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    cnts[ord(c) - ord('a')]+=1\n",
    "                elif 'A' <= c <= 'Z':\n",
    "                    cnts[ord(c) - ord('A')]+=1\n",
    "            return cnts\n",
    "        \n",
    "        cs = counter(licensePlate)\n",
    "        l, ans = inf, None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                ws, i = counter(w), 0\n",
    "                while i < len(cs):\n",
    "                    if ws[i] < cs[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(cs):\n",
    "                    l, ans = len(w), w\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        lic=[i.lower() for i in licensePlate if i.isalpha()]\n",
    "        d=Counter(lic)\n",
    "        words.sort(key=len)\n",
    "        for i in words:\n",
    "            for j in d:\n",
    "                if i.count(j)<d[j]:break\n",
    "            else:return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        temp = licensePlate.lower()\n",
    "        temp = temp.replace(\" \",\"\")\n",
    "        num = [\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"0\"]\n",
    "        for i in num:\n",
    "            temp = temp.replace(i,\"\")\n",
    "        c = Counter(temp)\n",
    "        mx = float(\"inf\")\n",
    "        mword = \"\"\n",
    "        for word in words:\n",
    "            if len(word) < len(temp):\n",
    "                continue\n",
    "            cw = list(Counter(word).items())\n",
    "            buquan = True\n",
    "            c_copy = c.copy()\n",
    "            for i in cw:\n",
    "                if i[0] in c_copy:\n",
    "                    if i[1] < c_copy[i[0]]:\n",
    "                        buquan = False\n",
    "                        break\n",
    "                    else:\n",
    "                        del c_copy[i[0]]\n",
    "            if len(c_copy) > 0:\n",
    "                buquan = False\n",
    "            if not buquan:\n",
    "                continue\n",
    "            if len(word) <mx:\n",
    "                mx = len(word)\n",
    "                mword = word\n",
    "        return mword\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        \n",
    "        dic = {}\n",
    "        for c in licensePlate.lower():\n",
    "            if c.isalpha():\n",
    "                dic[c] = dic.get(c, 0) + 1\n",
    "\n",
    "        res = ' ' * 1001\n",
    "        for word in words:\n",
    "            tmp_dic = dic.copy()\n",
    "            for c in word:\n",
    "                if c in dic and tmp_dic[c] > 0:\n",
    "                     tmp_dic[c] -= 1\n",
    "\n",
    "            if sum(tmp_dic.values()) == 0 and len(word) < len(res):\n",
    "                res = word\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        # print(words)\n",
    "        s = re.sub('[^a-zA-Z]+', '', licensePlate).lower()\n",
    "        s = sorted(s)\n",
    "        # print(s)\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        # print(words)\n",
    "        for w in words:\n",
    "            ws = sorted(w)\n",
    "            d = 0\n",
    "            for c in s:\n",
    "                if c in ws:\n",
    "                    ws.remove(c)\n",
    "                    d += 1\n",
    "            if d == len(s):\n",
    "                return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        a=Counter(i.lower() for i in licensePlate if i.isalpha())\n",
    "        return min((m for m in words if not a-Counter(m)),key=len)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def isbao(str1,str2):\n",
    "            for x in str1:\n",
    "                if x in str2:\n",
    "                    str2=str2.replace(x,'',1)\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        tar = str()\n",
    "        res = list()\n",
    "        for x in licensePlate:\n",
    "            if x.isalpha():\n",
    "                tar+=x.lower()\n",
    "        for y in words:\n",
    "            if isbao(tar,y):\n",
    "                res.append(y)\n",
    "                if len(y)<len(res[0]):\n",
    "                    res[0]=y\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def counter(word):\n",
    "            cnts = [0] * 26\n",
    "            for c in word:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    cnts[ord(c) - ord('a')]+=1\n",
    "                elif 'A' <= c <= 'Z':\n",
    "                    cnts[ord(c) - ord('A')]+=1\n",
    "            return cnts\n",
    "        \n",
    "        cs = counter(licensePlate)\n",
    "        l, ans = inf, None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                ws, i = counter(w), 0\n",
    "                while i < len(cs):\n",
    "                    if ws[i] < cs[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(cs):\n",
    "                    l, ans = len(w), w\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        c = Counter(char.lower() for char in licensePlate if char.isalpha())\n",
    "        return min((word for word in words if not(c - Counter(word))), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        c = Counter(char.lower() for char in licensePlate if char.isalpha())\n",
    "        return min((word for word in words if not (c-Counter(word))),key = len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        a=licensePlate.lower()\n",
    "        b=[]\n",
    "        o = []\n",
    "        c='abcdefghijklmnopqrstuvwxyz'\n",
    "        for i in range(len(a)):\n",
    "            if a[i] in c:\n",
    "                b.append(a[i])\n",
    "        res = \"\".join(b)\n",
    "\n",
    "        for i in words:\n",
    "            res1 = res\n",
    "            for j in i:\n",
    "                if j in res1:\n",
    "                    res1 = list(res1)\n",
    "                    res1.remove(j)\n",
    "            if len(res1) == 0:\n",
    "                o.append(i)\n",
    "        len1 = len(o[0])\n",
    "        for i in o:\n",
    "            if len1 > len(i):\n",
    "                len1 = len(i)\n",
    "\n",
    "        for i in o:\n",
    "            if len(i) == len1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def freq(s):\n",
    "    f = defaultdict(int)\n",
    "    for c in s:\n",
    "        if c.isalpha():\n",
    "            f[c.lower()] += 1\n",
    "    return f\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        fl = freq(licensePlate)\n",
    "        ans = 'a' * 16\n",
    "        for w in words:\n",
    "            fw = freq(w)\n",
    "            # print(fw)\n",
    "            if len(w) < len(ans) and all(fl[c] <= fw[c] for c in fl):\n",
    "                # print(fl, fw)\n",
    "                ans = w\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = collections.Counter(filter(str.isalpha,licensePlate.lower()))\n",
    "        return min(filter(lambda w:not (licensePlate-collections.Counter(w.lower())),words),key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key = len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "      # 1. 统计 licensePlate 中每个字母的出现次数（忽略大小写）\n",
    "      count = collections.Counter(chac.lower() for chac in licensePlate if chac.isalpha())\n",
    "      # 2. 遍历 words中的每个单词，若 26 个字母在该单词中的出现次数均不小于在 licensePlate 中的出现次数，则该单词是一个补全词。返回最短且最靠前的补全词\n",
    "      return min((word for word in words if not count-collections.Counter(word)), key = len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        # licenseMap = {}\n",
    "        licenseNew = \"\"\n",
    "        for ch in licensePlate.lower():\n",
    "            if 'a' <= ch and ch <= 'z':\n",
    "                # licenseMap[ch] += 1\n",
    "                licenseNew += ch\n",
    "        licenseCounter = Counter(licenseNew)\n",
    "        \n",
    "        maxlen = inf\n",
    "        res = \"\"\n",
    "        for word in words:\n",
    "            tmpCounter = Counter(word)\n",
    "            # print(licenseCounter - tmpCounter, len(licenseCounter-tmpCounter))\n",
    "            if len(licenseCounter-tmpCounter) == 0 and len(word) < maxlen:\n",
    "                maxlen = len(word)\n",
    "                res = word\n",
    "\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        target = {}\n",
    "        res = {}\n",
    "        for s in licensePlate:\n",
    "            if (ord(s) >= 65 and ord(s) <= 90) or (ord(s) >= 97 and ord(s) <= 122):\n",
    "                t = s.lower()\n",
    "                if t not in target:\n",
    "                    target[t] = 1\n",
    "                else:\n",
    "                    target[t] += 1\n",
    "        print(target)\n",
    "        for word in words:\n",
    "            flag = True\n",
    "            temp = {}\n",
    "            for s in word:\n",
    "                t = s.lower()\n",
    "                if s not in temp:\n",
    "                    temp[t] = 1\n",
    "                else:\n",
    "                    temp[t] += 1\n",
    "            for key, value in target.items():\n",
    "                if key not in temp or value > temp[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                temp[key]-=value\n",
    "            if flag:\n",
    "                res[word] = sum(temp.values())\n",
    "        minNum = min(res.values())\n",
    "        for word in words:\n",
    "            if word in res and res[word] == minNum:\n",
    "                return word\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        a={}\n",
    "        b,c=[],''\n",
    "        for i in licensePlate.lower():\n",
    "            if i.isalpha():\n",
    "                if i not in a:\n",
    "                    a[i]=1\n",
    "                else:\n",
    "                    a[i]+=1\n",
    "        for i in words:\n",
    "            for j in a:\n",
    "                c=i\n",
    "                if a[j]>i.lower().count(j):\n",
    "                    c=''\n",
    "                    break\n",
    "            b.append(c) if c!='' else b\n",
    "        return min(b,key=len)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        tar = []\n",
    "        for i in licensePlate:\n",
    "            if i.isalpha():\n",
    "                if i.isupper():\n",
    "                    i = i.lower()\n",
    "                tar.append(i)\n",
    "        cnt = Counter(tar)\n",
    "        # cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        tmp = max(words)\n",
    "        shortest_word = None\n",
    "        shortest_length = float('inf')\n",
    "        for word in words:\n",
    "            if not cnt - Counter(word):\n",
    "                if len(word) < shortest_length:\n",
    "                    shortest_length = len(word)\n",
    "                    shortest_word = word\n",
    "        return shortest_word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        #所有单词小写处理\n",
    "        pDict = dict()\n",
    "        for l in licensePlate.lower() :\n",
    "            if l.isalpha():\n",
    "                pDict.setdefault(l, 0)\n",
    "                pDict[l] += 1\n",
    "        result = \"\"\n",
    "        for w in words:\n",
    "            countW = Counter(w)\n",
    "            isStatisfied = True\n",
    "            for p, c in pDict.items():\n",
    "                if not (p in countW and c <= countW[p]) :\n",
    "                    isStatisfied = False\n",
    "                    break\n",
    "            if isStatisfied and (result == \"\" or len(w) < len(result)):\n",
    "                result = w\n",
    "            else:\n",
    "                isStatisfied = True\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = licensePlate.lower()\n",
    "        licenseDict = {}\n",
    "        for n in licensePlate: \n",
    "            if 122 >= ord(n) >= 97:\n",
    "                if n in licenseDict:\n",
    "                    licenseDict[n] += 1\n",
    "                else:\n",
    "                    licenseDict[n] = 1\n",
    "\n",
    "        i = 0\n",
    "        minL = 1000\n",
    "        for word in words:  \n",
    "            wordDict = {}\n",
    "            for nn in word:  \n",
    "                if nn in wordDict:\n",
    "                    wordDict[nn] += 1\n",
    "                else:\n",
    "                    wordDict[nn] = 1\n",
    "            isOK = True  \n",
    "            for key in licenseDict:\n",
    "                if key not in wordDict or wordDict[key] < licenseDict[key]:\n",
    "                    isOK = False\n",
    "                    break\n",
    "            if isOK:\n",
    "                if len(word) < minL:\n",
    "                    minL = len(word)\n",
    "                    minW = word\n",
    "        return minW\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        word = ''\n",
    "        for each in licensePlate:\n",
    "            if each.isalpha():\n",
    "                word += each.lower()\n",
    "\n",
    "        w = set(word)\n",
    "        n = len(set(w))\n",
    "\n",
    "        ans = []\n",
    "        for each in words:\n",
    "            count = 0\n",
    "            for i in w:\n",
    "                if each.count(i) >= word.count(i):\n",
    "                    count += 1\n",
    "            if count >= n:\n",
    "                ans.append(each)\n",
    "\n",
    "        res = []\n",
    "        for i, each in enumerate(words):\n",
    "            for item in ans:\n",
    "                if each == item:\n",
    "                    res.append([i, item])\n",
    "        res = sorted(res, key=lambda x: (len(x[1]), x[0]))\n",
    "\n",
    "        return res[0][1]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        list_str = []\n",
    "        for s in licensePlate:\n",
    "            if s == ' ' or s.isnumeric():\n",
    "                continue\n",
    "            list_str.append(s.lower())\n",
    "\n",
    "        def array_include(arr1: list, arr2: list):\n",
    "            list1 = [i for i in arr1]\n",
    "            list2 = [i for i in arr2]\n",
    "            for data in list1[::-1]:\n",
    "                if data in list2:\n",
    "                    list1.remove(data)\n",
    "                    list2.remove(data)\n",
    "            if list1:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        tar_list = []\n",
    "        for word in words:\n",
    "            if array_include(list_str, list(word)):\n",
    "                tar_list.append(word)\n",
    "        tar = tar_list[0]\n",
    "        for tar1 in tar_list:\n",
    "            if len(tar1) < len(tar):\n",
    "                tar = tar1\n",
    "        return tar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def counter(word):\n",
    "            cnts = [0] * 26\n",
    "            for c in word:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    cnts[ord(c) - ord('a')]+=1\n",
    "                elif 'A' <= c <= 'Z':\n",
    "                    cnts[ord(c) - ord('A')]+=1\n",
    "            return cnts\n",
    "        \n",
    "        cs = counter(licensePlate)\n",
    "        l, ans = inf, None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                ws, i = counter(w), 0\n",
    "                while i < len(cs):\n",
    "                    if ws[i] < cs[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(cs):\n",
    "                    l, ans = len(w), w\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(c for c in licensePlate.lower() if c.isalpha())\n",
    "        ans = 0\n",
    "        mn = inf\n",
    "        for i, w in enumerate(words):\n",
    "            if len(w) < mn and Counter(w) >= cnt:\n",
    "                mn = len(w)\n",
    "                ans = i\n",
    "        return words[ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        def check(d,wd):\n",
    "            for c in wd:\n",
    "                if wd[c]<d[c]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        licensePlate=licensePlate.lower()\n",
    "        d={}\n",
    "        for c in licensePlate:\n",
    "            if c.islower():\n",
    "                if c not in d:\n",
    "                    d[c]=1\n",
    "                else:\n",
    "                    d[c]+=1\n",
    "        least_length=1000000\n",
    "        for word in words:\n",
    "            wd={x:0 for x in d}\n",
    "            for w in word:\n",
    "                if w in wd:\n",
    "                    wd[w]+=1\n",
    "            if check(d,wd) and len(word)<least_length:\n",
    "                least_length=len(word)\n",
    "                result=word\n",
    "        \n",
    "        return result\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        str_lic = ''\n",
    "        for i in licensePlate:\n",
    "            if i.isalpha():\n",
    "                str_lic += i.lower()\n",
    "        str_lic = Counter(str_lic)\n",
    "        # print(str_lic)\n",
    "        answer = \"\"\n",
    "        for ele in words:\n",
    "            k = Counter(ele)\n",
    "            if not (str_lic - k):\n",
    "                if len(answer) == 0:\n",
    "                    answer = ele\n",
    "                else:\n",
    "                    if len(ele) < len(answer):\n",
    "                        answer = ele\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = collections.Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt-collections.Counter(word)), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        tmp=[]\n",
    "        for i in licensePlate:\n",
    "            if 'a'<=i<='z' or 'A'<=i<='Z':\n",
    "                tmp.append(i.lower())\n",
    "        words=sorted(words, key=lambda x:len(x))\n",
    "\n",
    "        for word in words:\n",
    "            l=tmp.copy()\n",
    "            for i in word:\n",
    "                if i in l:\n",
    "                    l.remove(i)\n",
    "                if not l:\n",
    "                    return word\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\r\n",
    "        def counter(word):\r\n",
    "            cnts = [0] * 26\r\n",
    "            for c in word:\r\n",
    "                if 'a' <= c <='z':\r\n",
    "                    cnts[ord(c) - ord('a')] += 1\r\n",
    "                elif 'A' <= c <= 'Z':\r\n",
    "                    cnts[ord(c) - ord('A')] += 1\r\n",
    "            return cnts\r\n",
    "\r\n",
    "        cs = counter(licensePlate)\r\n",
    "        length, answer = float(\"inf\"), None\r\n",
    "        for w in words:\r\n",
    "            if len(w) < length:\r\n",
    "                ws, i = counter(w), 0\r\n",
    "                while i < 26:\r\n",
    "                    if ws[i] < cs[i]:\r\n",
    "                        break\r\n",
    "                    i += 1\r\n",
    "                if i == 26:\r\n",
    "                    length, answer = len(w), w\r\n",
    "        return answer\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        o = 97\n",
    "        counter = [0] * 26\n",
    "        for ch in filter(lambda ch : ch.isalpha(), licensePlate):\n",
    "            counter[ord(ch.lower()) - o] += 1\n",
    "        words.sort(key = len) \n",
    "        for d in words:\n",
    "            copy = counter[:]\n",
    "            for ch in d:\n",
    "                index = ord(ch) - o\n",
    "                copy[index] = max(0, copy[index] - 1)\n",
    "            if not any(copy): \n",
    "                return d\n",
    "        return \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def freq(s):\n",
    "    return Counter(c.lower() for c in s if c.isalpha())\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        fl = freq(licensePlate)\n",
    "        # print([c for c in fl])\n",
    "        ans = 'a' * 16\n",
    "        for w in words:\n",
    "            if len(w) < len(ans) and fl <= Counter(w):\n",
    "                # print(fl, fw)\n",
    "                ans = w\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate, words):\n",
    "        cnt = Counter(c.lower() for c in licensePlate if c.isalpha())\n",
    "        return min((word for word in words if not cnt - Counter(word)), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        lic = licensePlate.lower()\n",
    "        l = {}\n",
    "        for c in lic:\n",
    "            if(c == \" \" or c.isdigit()):\n",
    "                continue\n",
    "            if c in l: \n",
    "                l[c] += 1\n",
    "            else:\n",
    "                l[c] = 1\n",
    "        \n",
    "        ret = \"\"\n",
    "        length = 1000\n",
    "        for w in words:\n",
    "            w = w.lower()\n",
    "            flag = 1\n",
    "            for k, v in l.items():\n",
    "                if w.count(k) < v:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if(flag):\n",
    "                if(len(w) < length):\n",
    "                    length = len(w)\n",
    "                    ret = w \n",
    "\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, LP: str, W: List[str]) -> str:\n",
    "        c = Counter(ch.lower() for ch in LP if ch.isalpha())\n",
    "        return next(w for w in sorted(W, key=len) if c & Counter(w) == c)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = licensePlate.lower()\n",
    "        count = collections.Counter()\n",
    "        for c in licensePlate:\n",
    "            if 'a' <= c <= 'z':\n",
    "                count[c] += 1\n",
    "        ans = ''\n",
    "        for word in words:\n",
    "            c1 = collections.Counter(word)\n",
    "            flag = True\n",
    "            for key in count.keys():\n",
    "                if c1[key] < count[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag and (len(word) < len(ans) or ans == ''):\n",
    "                ans = word\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        dic = {}\n",
    "        for i in licensePlate:\n",
    "            if i.isalpha():\n",
    "                i = i.lower()\n",
    "                if i in dic:\n",
    "                    dic[i] += 1\n",
    "                else:\n",
    "                    dic[i] = 1\n",
    "        res = []\n",
    "        length = float(\"inf\")\n",
    "        print(dic)\n",
    "        for word in words:\n",
    "            temp = {}\n",
    "            word = word.lower()\n",
    "            for i in word:\n",
    "                temp[i] = word.count(i)\n",
    "            flag = True\n",
    "            print(temp)\n",
    "            for i in dic:\n",
    "                if i not in temp:\n",
    "                    print(\"*\")\n",
    "                    flag = False\n",
    "                    break\n",
    "                if dic[i]>1 and temp[i]<dic[i]:\n",
    "                    print(i)\n",
    "                    flag = False\n",
    "                elif dic[i] == 1 and temp[i] < dic[i]:\n",
    "                    \n",
    "                    flag = False\n",
    "            if flag:\n",
    "                if len(word)<length:\n",
    "                    res = [word]\n",
    "                    length = len(word)\n",
    "                elif len(word) == length:\n",
    "                    res.append(word)\n",
    "            print(res)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        str_lic = ''\n",
    "        for i in licensePlate:\n",
    "            if i.isalpha():\n",
    "                str_lic += i.lower()\n",
    "        str_lic = Counter(str_lic)\n",
    "        # print(str_lic)\n",
    "        answer = \"\"\n",
    "        for ele in words:\n",
    "            k = Counter(ele)\n",
    "            if not (str_lic - k):\n",
    "                if len(answer) == 0:\n",
    "                    answer = ele\n",
    "                else:\n",
    "                    if len(ele) < len(answer):\n",
    "                        answer = ele\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        words = sorted(words, key=len)\n",
    "        dc = defaultdict(int)\n",
    "        for c in licensePlate:\n",
    "            if c.isalpha():\n",
    "                dc[c.lower()] += 1\n",
    "\n",
    "        for w in words:\n",
    "            dc_ = defaultdict(int)\n",
    "            for c in w:\n",
    "                if c in dc.keys():\n",
    "                    dc_[c] += 1\n",
    "            flag = True\n",
    "            for k in dc.keys():\n",
    "                if k not in dc_.keys():\n",
    "                    flag = False\n",
    "                    break\n",
    "                if dc[k] > 1:\n",
    "                    if dc[k] != dc_[k]:\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                return w\n",
    "        \n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        words = sorted(words, key= lambda x:len(x))\n",
    "        tar = []\n",
    "        for i in licensePlate:\n",
    "            if i.isalpha():\n",
    "                if i.isupper():\n",
    "                    i = i.lower()\n",
    "                tar.append(i)\n",
    "        # print(tar)\n",
    "        # print('words=', words)\n",
    "        for word in words:\n",
    "            list_word = list(word)\n",
    "            # print('0list_word=',list_word)\n",
    "            for i in range(len(tar)):\n",
    "                if tar[i] not in list_word:\n",
    "                    break\n",
    "                else:\n",
    "                    # print('list_word=', list_word)\n",
    "                    list_word.remove(tar[i])\n",
    "                if i == len(tar) - 1:\n",
    "                    return word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: list[str]) -> str:\n",
    "        def count(s):\n",
    "            s = s.lower()\n",
    "            sdic = {}\n",
    "            for c in s:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    if c in sdic:\n",
    "                        sdic[c] += 1\n",
    "                    else:\n",
    "                        sdic[c] = 1\n",
    "            return sdic\n",
    "\n",
    "        licensedic = count(licensePlate)\n",
    "        l = float('inf')\n",
    "        res = None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                wdic = count(w)\n",
    "                Flag = True\n",
    "                for k in licensedic:\n",
    "                    if (k not in wdic) or (wdic[k] < licensedic[k]):\n",
    "                        Flag = False\n",
    "                        break\n",
    "                if Flag:\n",
    "                    res = w\n",
    "                    l = len(w)\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    licensePlate = \"1s3 PSt\"\n",
    "    words = [\"step\", \"steps\", \"stripe\", \"stepple\"]\n",
    "    print(obj.shortestCompletingWord(licensePlate, words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = licensePlate.lower()\n",
    "        # print(licensePlate)\n",
    "        d1 = defaultdict(int)\n",
    "        for c in licensePlate:\n",
    "            if 'a' <= c <= 'z':\n",
    "                d1[c] += 1\n",
    "        #\n",
    "        mn = 16\n",
    "        ret = \"\"\n",
    "        for word in words:\n",
    "            if mn > len(word):\n",
    "                d2 = d1.copy()\n",
    "                canfill = True\n",
    "                for c in word:\n",
    "                    d2[c] -= 1\n",
    "                for c in d2.keys():\n",
    "                    if d2[c] > 0:\n",
    "                        canfill = False\n",
    "                        break\n",
    "                # print(d1, d2)\n",
    "                if canfill:\n",
    "                    ret = word\n",
    "                    mn = len(word)\n",
    "        #\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        tmp=[]\n",
    "        for i in licensePlate:\n",
    "            if 'a'<=i<='z' or 'A'<=i<='Z':\n",
    "                tmp.append(i.lower())\n",
    "        words=sorted(words, key=lambda x:len(x))\n",
    "\n",
    "        for word in words:\n",
    "            l=tmp.copy()\n",
    "            for i in word:\n",
    "                if i in l:\n",
    "                    l.remove(i)\n",
    "                if not l:\n",
    "                    return word\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if Counter(word) >= cnt), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        return min((word for word in words if Counter(word) >= cnt), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate, words):\n",
    "        allWords = []\n",
    "        dict1 = {}\n",
    "        for a in licensePlate:\n",
    "            if a.isalpha():\n",
    "                if a.isupper():\n",
    "                    a = a.lower()\n",
    "                if a not in dict1:\n",
    "                    dict1[a] = 1\n",
    "                else:\n",
    "                    dict1[a] += 1\n",
    "        for word in words:\n",
    "            cnt = 0\n",
    "            for c in dict1:\n",
    "                if word.count(c) >= dict1[c]:\n",
    "                    cnt += 1\n",
    "            if cnt == len(dict1):\n",
    "                allWords.append(word)\n",
    "        allWord = min(allWords,key=len)\n",
    "        return allWord\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        s = [float('inf'), 0]\n",
    "        z = Counter([i if ord(i) in range(97, 123) else '' for i in licensePlate.lower()])\n",
    "        del z['']\n",
    "        for i in range(len(words)):\n",
    "            c = Counter(words[i])\n",
    "            for j in z:\n",
    "                if not z.get(j) or c[j] < z[j]:\n",
    "                    break\n",
    "            else:\n",
    "                if len(words[i]) < s[0]:\n",
    "                    s = [len(words[i]), i]\n",
    "        return words[s[1]]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]):\n",
    "        c = Counter(ch.lower() for ch in licensePlate if ch.isalpha())\n",
    "        for i in sorted(words,key=len):\n",
    "            if c & Counter(i) == c:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "\n",
    "        exits = collections.defaultdict(int)\n",
    "\n",
    "        for c in licensePlate:\n",
    "            if c.isdigit() or c == \" \": continue\n",
    "            exits[c.lower()] += 1\n",
    "        \n",
    "        res = None\n",
    "        for word in words:\n",
    "\n",
    "\n",
    "            curExist = collections.defaultdict(int)\n",
    "            for c in word:\n",
    "                if c.isdigit() or c == \" \": continue\n",
    "                curExist[c.lower()] += 1\n",
    "            flag = True\n",
    "            for k in exits:\n",
    "\n",
    "                if k not in curExist or curExist[k] < exits[k]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if not flag: continue\n",
    "\n",
    "            if not res:\n",
    "                res = word\n",
    "            else:\n",
    "                if len(res) > len(word):\n",
    "                    res = word\n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        res=[]\n",
    "        for c in licensePlate:\n",
    "            if c.isalpha():\n",
    "                res.append(c.lower())\n",
    "        st=''.join(res)\n",
    "        print(st)\n",
    "        words=sorted(words,key=lambda x:len(x))\n",
    "        print(words)\n",
    "        for word in words:\n",
    "            l=res.copy()\n",
    "            for i in word:\n",
    "                if i in l:\n",
    "                    l.remove(i)\n",
    "                if not l:\n",
    "                    return word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        cnt = Counter(ch for ch in licensePlate.lower() if ch.isalpha())\n",
    "        return min((word for word in words if Counter(word) >= cnt), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = licensePlate.lower()\n",
    "        licenseDict = {}\n",
    "        for n in licensePlate:  #目标字符串字典\n",
    "            if 122 >= ord(n) >= 97:\n",
    "                if n in licenseDict:\n",
    "                    licenseDict[n] += 1\n",
    "                else:\n",
    "                    licenseDict[n] = 1\n",
    "\n",
    "        i = 0\n",
    "        minL = 1000\n",
    "        for word in words:  #每存成一次字典就原地比较，不用开拓新的数组\n",
    "            wordDict = {}\n",
    "            for nn in word:   #把当前字符保存成字典\n",
    "                if nn in wordDict:\n",
    "                    wordDict[nn] += 1\n",
    "                else:\n",
    "                    wordDict[nn] = 1\n",
    "            isOK = True   #与目标字符串字典比较\n",
    "            for key in licenseDict:\n",
    "                if key not in wordDict or wordDict[key] < licenseDict[key]:\n",
    "                    isOK = False\n",
    "                    break\n",
    "            if isOK:\n",
    "                if len(word) < minL:\n",
    "                    minL = len(word)\n",
    "                    minW = word\n",
    "        return minW\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "\n",
    "        def counter(word):\n",
    "            cnts = [0] * 26\n",
    "            for c in word:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    cnts[ord(c)- ord('a')] += 1\n",
    "                else:\n",
    "                    if 'A' <= c <= 'Z':\n",
    "                        cnts[ord(c) - ord('A')] += 1\n",
    "            return cnts\n",
    "        \n",
    "        cs = counter(licensePlate)\n",
    "        print(cs)\n",
    "        l, ans = inf, None\n",
    "        for w in words:\n",
    "            if len(w) < l:\n",
    "                ws, i = counter(w), 0\n",
    "                print(w, ws)\n",
    "                while i < len(cs):\n",
    "                    if ws[i] < cs[i]:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(cs):\n",
    "                    l, ans = len(w), w\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:\n",
    "        licensePlate = sorted(list(filter(lambda x: not (ord(x)>=ord('0') and ord(x)<=ord('9')) and x!=' ', [_ for _ in licensePlate.lower()])))\n",
    "        residx = -1\n",
    "        for idx, word in enumerate(words):\n",
    "            strs = sorted([_ for _ in word])\n",
    "            i, j = 0, 0\n",
    "            while i<len(licensePlate) and j<len(strs):\n",
    "                if licensePlate[i] == strs[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    while j<len(strs) and licensePlate[i] != strs[j]:\n",
    "                        j += 1\n",
    "            if i==len(licensePlate):\n",
    "                if residx==-1 or len(word)<len(words[residx]):\n",
    "                    residx = idx\n",
    "        return words[residx]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
